package Leetcode.sliding_window;

/**
 * @Author: kirito
 * @Date: 2024/3/25 16:36
 * @Description:
 * 给你字符串 s 和整数 k 。
 *
 * 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
 *
 * 英文中的 元音字母 为（a, e, i, o, u）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "abciiidef", k = 3
 * 输出：3
 * 解释：子字符串 "iii" 包含 3 个元音字母。
 * 示例 2：
 *
 * 输入：s = "aeiou", k = 2
 * 输出：2
 * 解释：任意长度为 2 的子字符串都包含 2 个元音字母。
 * 示例 3：
 *
 * 输入：s = "leetcode", k = 3
 * 输出：2
 * 解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
 * 示例 4：
 *
 * 输入：s = "rhythms", k = 4
 * 输出：0
 * 解释：字符串 s 中不含任何元音字母。
 * 示例 5：
 *
 * 输入：s = "tryhard", k = 4
 * 输出：1
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 10^5
 * s 由小写英文字母组成
 * 1 <= k <= s.length
 */

public class maxVowels {
    public static void main(String[] args) {
        String s = "weallloveyou";
        int k = 7;
        //输出3  预期4
        System.out.println(maxVowels(s, k));
    }
    /**
     * 长度为K里面包含最多元音字母数
     * 那就直接i，i+k  遍历，然后count
     *
     * 超时了。。。emmmmmmm
     *
     * 这个算法每次移动一位的时候，只有首末才会更新count，中间的都是重复判断
     * 所以可以从这个方向入手优化速率
     * @param s
     * @param k
     * @return
     */
    public static int maxVowels1(String s, int k) {
        int len = s.length();//12
        char[] chars = s.toCharArray();
        int res = 0;
        for (int i = 0; i < len - k + 1; i++) {
            int count = 0;
            for (int j = i; j < i + k; j++) {
                count += isVowel(chars[j]);
            }
            res = Math.max(res, count);
        }
        return res;
    }

    /**
     * 先遍历一次，看哪一位是  就数组设置为1
     * 然后在双重遍历求和取值
     * 但是总体时间复杂度是一样的，只是少了一个函数判断元音字母的调用
     *
     * 未超时，但是执行时间很长，所以这个优化不是很明显，所以还是得尊长第一次的那个算法逻辑入手
     * @param s
     * @param k
     * @return
     */
    public static int maxVowels2(String s, int k) {
        int len = s.length();//12
        char[] chars = s.toCharArray();
        int[] ints = new int[len];
        for (int i = 0; i < len; i++) {
            ints[i] = isVowel(chars[i]);
        }
        int res = 0;
        for (int i = 0; i < len - k + 1; i++) {
            int count = 0;
            for (int j = i; j < i + k; j++) {
                count += ints[j];
            }
            res = Math.max(res, count);
        }
        return res;
    }

    /**
     * 首先计算初始窗口[0,k]中元音字母的个数，然后这个窗口开始向右滑动一格，此时分为三种情况：
     *
     * 右侧新进入窗口的字母为元音字母，左侧移出窗口的字母也是元音字母，这样一进一出抵消掉了
     * 右侧新进入窗口的字母为元音字母，左侧移出窗口的字母非元音字母，此时元音字母个数+1
     * 右侧新进入窗口的字母非元音字母，左侧移出窗口的字母为元音字母，此时元音字母个数-1
     * 综上->vowel_count += isVowel(s[i]) - isVowel(s[i - k]);
     */
    public static int maxVowels(String s, int k) {
        int n = s.length();
        int vowel_count = 0;
        int[] ints = new int[n];
        //空间换时间了，就不用每次就去调那个判断方法了= =有点画蛇添足
        for (int i = 0; i < n; i++) {
            ints[i] = isVowel(s.charAt(i));
        }
        for (int i = 0; i < k; ++i) {
            vowel_count += isVowel(s.charAt(i));
        }
        int ans = vowel_count;
        for (int i = k; i < n; ++i) {
            vowel_count += ints[i] - ints[i - k];
            ans = Math.max(ans, vowel_count);
        }
        return ans;
    }


    public static int isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
    }
}
